import java.util.Scanner;

public class Test {
    public static void main(String[] args) {
        int t1;
        int n;
        int k;
        String s;
        Scanner sc = new Scanner(System.in);
        t1=sc.nextInt();
        //循环t1次
        while (t1>0){
            n = sc.nextInt();
            k = sc.nextInt();
            sc.nextLine();
            s = sc.nextLine();
            //用数组来存储01String
            String[] strings = new String[k+1];
            //将s0存入数组第一个
            strings[0]=s;
            for (int i=0;i<k;i++){
                String output = output(strings[i]);
                strings[i+1] = output;
            }

            //输出1的个数
            int out = out(strings);
            System.out.println(out);
            t1--;
        }
    }

    //计算1的个数
    public static int out(String[] s){
        //记录1的个数
        int sum=0;

        for (int i=0;i<s.length;i++){
            String s1 = s[i];
            int length = s1.length();
            for (int k=0;k<length;k++){
                //字符为1
                if (s1.charAt(k)=='1'){
                    sum++;
                }
            }
        }
        return sum;
    }

    //计算si
    public static String  output(String s){
        String temp ="";
        int length = s.length();

        for (int i=0;i<length-1;i++){
            char c1 = s.charAt(i);
            char c2 = s.charAt(i + 1);
            //如果c1和c2有一个为1则字符串第i位为1
            if (c1=='1'||c2=='1'){
                temp+='1';
            }else {
                //反之则为0
                temp+='0';
            }
        }
        return temp;
    }
}
